Papers^γ

### Style I like the Levin style, he writes a bit provocative phrases that looks, in the same time, incredibly truthful (at least for the author himself). Consider for example what he says about the invention of positional numeral systems and Quantum computers: > Archimedes made a great discovery that digital representation of numbers is exponentially > more efficient than analog ones (sand pile sizes). Many subsequent analog devices yielded > unimpressive results. It is not clear why QCs [quantum computers] should be an exception. ### One-way function and the axiom of choice One-way functions and the axiom of choice deals with practical or conceptual (im-)possibility to solve [inverse problems](https://en.wikipedia.org/wiki/Inverse_problem) arising in Computer Science and Mathematics. ### Kolmogorov complexity and One-way functions Two primes $p$ and $q$ have almost the same [informational content](https://en.wikipedia.org/wiki/Algorithmic_information_theory) as their product $pq$. However, the [$p, q \mapsto pq$](https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Arithmetic_functions) is much more easy to do than [$pq \mapsto p,q$](https://en.wikipedia.org/wiki/Integer_factorization#Prime_decomposition).